package com.leet.code.medium_array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @description:    15.三数之和
 * @author: WYG
 * @time: 2021/1/6 9:13
 */

public class ThreeSum {

    /**
     * 思路:排序加双指针
     * 题目是求三数之和，并且要求不重复，如果直接使用三重for循环的话不仅会增加时间复杂度，而且会有重复的答案。所以要另想他法
     * 既然要求三数之和不重复，那么我们可以对数组进行排序，然后遍历的时候跳过相同大小的数据元素，进而引出了下面的解法
     * 首先，对数组进行排序，java可以使用Arrays.sort()降低排序的难度
     * 然后，对排序后的数组进行遍历，遍历的过程中分为多种情况：
     * 1、如果遍历排序后的数组时，第一个遍历到的元素大于0，那么其后续的元素也都大于0，就不存在相加为0的三数，就可以结束遍历
     * 2、如果遍历的元素和上一个元素相同的话，那么该元素所得的结果和上个元素会是一样的，可以跳过这次循环继续下次循环
     * 3、然后利用双指针的方式遍历数组：
     *  (1)如果nums[a] + nums[b] + nums[i] == 0，那么就满足题目的条件，可以将这三个元素加入结果数组中，然后a--，b++，
     *  再比较a和b的大小以及nums[a]和它的前一个元素，nums[b]和它的后一个元素是否相等，如果相等的话就是那么接下来的结果就和上次的结果相同，
     *  继续a++或者b--，继续寻找新的解
     *  (2)当nums[a] + nums[b] + nums[i] < 0时，说明nums[a]太小了，需要向后遍历
     *  (3)当nums[a] + nums[b] + nums[i] > 0时，说明nums[b]太大了，需要向前遍历
     * @param nums  待求和数组
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) break; // 第一个数大于 0，后面的数都比它大，肯定不成立了
            if (i > 0 && nums[i] == nums[i - 1]) continue; // 去掉重复情况
            //双指针左侧
            int a = i + 1;
            //双指针右侧
            int b = nums.length - 1;
            //遍历
            while (a < b) {
                if (nums[a] + nums[b] + nums[i] == 0) {
                    res.add(Arrays.asList(nums[i], nums[a], nums[b]));
                    a++;
                    b--;
                    while (a < b && nums[a] == nums[a - 1]) a++;
                    while (a < b && nums[b] == nums[b + 1]) b--;
                }
                if (nums[a] + nums[b] + nums[i] < 0) {
                    a++;
                }
                if (nums[a] + nums[b] + nums[i] > 0) {
                    b--;
                }
            }
        }
        return res;
    }
}
